package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @class Code54
 * @description 剑指 Offer 51. 数组中的逆序对
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [7,5,6,4]
 * 输出: 5
 *  
 *
 * 限制：
 *
 * 0 <= 数组长度 <= 50000
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-13 11:40
 */
public class Code54 {
    public static void main(String[] args) {
        int[] nums = new int[]{7,5,6,4};
        System.out.println(reversePairs(nums));
    }

    public static int counter;

    public static int reversePairs(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        counter = 0;
        getReverseNumber(nums, 0, len - 1);
        return counter;
    }

    private static int[] getReverseNumber(int[] arr, int left, int right) {
        if (left == right) {
            return new int[]{arr[left]};
        }
        int mid = (left + right) >> 1, resIndex = 0, leftIndex = 0, rightIndex = 0;
        int[] res = new int[right - left + 1], leftSorted = getReverseNumber(arr, left, mid), rightSorted = getReverseNumber(arr, mid + 1, right);
        while (leftIndex < leftSorted.length && rightIndex < rightSorted.length) {
            int leftNum = leftSorted[leftIndex];
            int rightNum = rightSorted[rightIndex];
            if (leftNum <= rightNum) {
                res[resIndex++] = leftNum;
                leftIndex++;
            } else {
                res[resIndex++] = rightNum;
                counter += (leftSorted.length - leftIndex);
                rightIndex++;
            }
        }

        while (leftIndex < leftSorted.length) {
            res[resIndex++] = leftSorted[leftIndex++];
        }

        while (rightIndex < rightSorted.length) {
            res[resIndex++] = rightSorted[rightIndex++];
        }

        return res;
    }
}
/*
归并排序的思想，每次归并的时候如果右边的数组放入结果中的时候，计数器则增加左边数组剩下数字的数量
 */